package gdut.edu.demo04;

import java.util.Arrays;

/**
 * @Description 基数排序
 * @Author JiaFu
 * @Date 2022/11/11 19:58
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 123, 34, 567, 8, 99, 765, 234, 2, 11, 33, 778, 0};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void radixSort(int[] arr) {
        //取出最大数字的长度
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //最大数字的长度
        int maxLength = (max + "").length();
        //用于临时存储数据的数组
        int[][] tempArr = new int[10][arr.length];
        //记录临时数组中各个数组存放元素的个数
        int[] counts = new int[10];
        //根据最大数字的长度决定比较次数
        for (int j = 0, n = 1; j < maxLength; j++, n *= 10) {
            //把每个数字分别计算余数,将数据存放到临时数组
            for (int k = 0; k < arr.length; k++) {
                //计算余数
                int ys = (arr[k] / n) % 10;
                //将数据存放到临时数组
                tempArr[ys][counts[ys]] = arr[k];
                //存放个数+1
                counts[ys]++;
            }
            //记录取出临时数组数据存放到原来数据arr的位置
            int index = 0;
            //存完数据之后取出数据到原来的数组arr[]
            for (int l = 0; l < counts.length; l++) {
                //临时数组存放有数据，取出放回原数组
                if (counts[l] != 0) {
                    for (int i = 0; i < counts[l]; i++) {
                        arr[index] = tempArr[l][i];
                        index++;
                    }
                }
                //把数量置为0
                counts[l] = 0;
            }
        }

    }
}
